The present invention relates generally to keyboards, and more particularly to predicting keystrokes on a single pointer keyboard.
In traditional keyboards, the keys representing the various characters or symbols in a written language are typically arranged in rows in such a way that typing with two hands is rapid and efficient. However, traditional keyboards require extensive training and practice before full proficiency is attained. An untrained user types by tedious hunting and pecking. With a keyboard arranged in the most common xe2x80x9cQWERTYxe2x80x9d arrangement, the untrained user is faced with an apparently random distribution of keys, and the speed at which the keyboard can be operated suffers tremendously. In fact, the xe2x80x9cQWERTYxe2x80x9d arrangement is not random; it was actually designed to limit two-handed typing speed.
The speed at which an untrained user can operate a keyboard can be usefully studied with a simple user interaction model that breaks down user actions into three stages: scanning, deciding, and physically selecting. The time to complete an action is the sum of the delays incurred at each stage, for example:
Total time or cost to type a key=Tv+Tc+Tm
where Tv is the visual load, Tc the cognitive load, and Tm the motor load.
An important part of the visual load is the eye movements that must be made while hunting for a key. The organization of photoreceptors in the eye is such that the vast majority of the receptors are located in a small region in the center of the retina called the fovea, a window that receives light stimuli subtending approximately 1xc2x0 of the visual field. Similarly, most of the brain""s visual intelligence is concentrated on this small area. Visual tasks such as shape recognition and reading require that the eye be oriented so that the image of the object in question is projected onto or very near the fovea.
Therefore, while hunting for a key, it is necessary to repeatedly re-orient the eye so that the images of each of many randomly distributed keys project onto this high-resolution area. Only then can detailed perceptual analysis begin. The method by which eyes are oriented is known as a saccadexe2x80x94an oculomotor reaction that moves the eyeball such that the image of interest is foveated. To compound the problem, if the eye movement is large, the saccade may miss the target and further delays are incurred as the eye position is adjusted.
An efficient keyboard should minimize saccades. Ideally, the most frequently used portion of the keyboard should be visually compact, so that this portion is mostly contained in the fovea. Equally important, when necessary, saccades should be small. The less the eyes move and the more visually stable the keyboard, the faster hunting and pecking can proceed. Obviously, most xe2x80x9cstandardxe2x80x9d keyboards, with a length of almost a foot and a half, and an aspect ratio as high as five to one, are ill suited for casual hunt-and-peck users.
In the context of typing, cognitive load refers to work done while deciding between keys, and planning where to look or point next. Deciding and planning are memory-limited processes. It takes longer to decide between many alternatives. Not just because there are more, but also because short-term memory is quite limited. When there are too many alternatives, some must be moved in and out of short-term memory, for example, by looking at the keyboard again. Typically, people can choose amongst two or three alternatives quickly but slow down considerably when faced with five or more choices.
If the keyboard is laid out in a meaningful manner, such as an alphabetic order, then the cognitive load is somewhat reduced because the mind does not need to plan out a search strategy for finding the next appropriate key. If the user does not have perfect knowledge of the location of each letter, then some searching is unavoidable. In that case, cognitive load can be reduced by embedding familiar patterns in the arrangement of the keys, for example, by placing the letters of mnemonic sequences such as xe2x80x9cquxe2x80x9d, xe2x80x9cthxe2x80x9d, xe2x80x9cingxe2x80x9d on adjacent keys. Having seen xe2x80x9cqxe2x80x9d the user has strong expectations about where to find the following xe2x80x9cuxe2x80x9d. Providing familiar patterns to the user also reduces cognitive load because a familiar pattern or relationship imposes less working memory load than its individual constituents.
A good keyboard should not require a lot of pointer travel, or highly precise motions. It is easy to make small, incremental motions, e.g., to move to an adjacent key, but hard to land precisely on a key that is far away. One way of reducing motor load is by making targets as large and round as possible. This suggests laying the keys out as hexagonal tiles in a triangular grid.
U.S. Pat. No. 4,579,470 teaches a keyboard with keys clustered in a hexagonal-like pattern. The clustering attempts to minimize finger movement for a two-handed user. That keyboard has no special properties for hunt-and-peck typing.
U.S. Pat. No. 5,128,672 describes a predictive xe2x80x9csoft keyboard.xe2x80x9d The set of twelve keys that are displayed depend on the frequency of a particular character combination being used in a particular language. For example, one character set is displayed after a vowel, and another after a constant. The object is to provide a keyboard with a minimal number of keys, i.e., twelve. A tough-sensitive hand-held implementation is suggested. Statistical analysis of linguistic characteristics is vaguely described for making the predication about which character set to display at a given instant.
In U.S. Pat. No. 5,487,616, the arrangement is designed by a greedy search procedure which permutes the character-to-key assignments and keeps the permutation when the permutation has a lower expected travel. By definition, greedy search procedure usually only find mediocre locally optimal solutions.
U.S. Pat. No. 5,625,354 describes a hexagonal xe2x80x9chunt and peckxe2x80x9d keyboard which has keys arranged in a xe2x80x9choneycombxe2x80x9d type of pattern to minimize the distance between individual keys. More frequently occurring pairs of letters are clustered in close proximity to the center of the keyboard. The clustering is based on digraphs, specific frequencies of pairs of characters. A stylus is suggested to peck at the keys. However, there is no attempt to minimize the total distance that the stylus must move to enter text for a particular language.
U.S. Pat. No. 5,805,157 describes a xe2x80x9csoft keyboardxe2x80x9d with hexagonal keys. Hexagonal shape was chosen to facilitate discrimination of closed-spaced keys during pecking, and key spacing can be more dense. A mouse is suggested for the pointing, and a cursor xe2x80x9csnapsxe2x80x9d to the key. No attempt was made to optimize the keyboard for a particular language.
U.S. Pat. No. 6,011,554 describes a disambiguating keyboard with twelve keys. Multiple characters are assigned to each key, making keystrokes ambiguous. The ambiguous sequence is resolved by use of a library of prestored sequences.
Keys are arranged on a keyboard as follows. A training corpus of input symbol sequences is provided, for example, informal written English texts. Each unique symbol in the corpus has an associated key on the keyboard. A cost function that measures a cost C of inputting the symbols of the training corpus is globally minimized. Then, the keys are arranged on the keyboard according to the globally minimized cost function. To reduced the distance a pointer must move, the keys can also be arranged in a hexagonal pattern.
Keystrokes on a keyboard are predicted by constructing a model from a training corpus. The training corpus includes symbol sequences. The model predicts a set of symbols, where each symbol of the set continues a particular symbol sequence using variable-length subsequences of the particular symbol sequence. A particular length is chosen to maximize a probability that the predicting is correct. Keys on the keyboard are highlighted. The highlighted keys correspond to selected symbols in the set of symbols.